/*
 * contrib/pg_trgm/trgm_gist.c
 */
#include "postgres.h"

#include "access/reloptions.h"
#include "access/stratnum.h"
#include "fmgr.h"
#include "port/pg_bitutils.h"
#include "trgm.h"

/* gist_trgm_ops 操作类选项 */
typedef struct
{
	int32		vl_len_;		/* varlena 头部（请勿直接触摸！） */
	int			siglen;			/* 签名长度（字节） */
} TrgmGistOptions;

#define GET_SIGLEN()			(PG_HAS_OPCLASS_OPTIONS() ? \
								 ((TrgmGistOptions *) PG_GET_OPCLASS_OPTIONS())->siglen : \
								 SIGLEN_DEFAULT)

typedef struct
{
	/* 最近的 gtrgm_consistent 输入 */
	StrategyNumber strategy;
	text	   *query;
	/* 查询的提取三元组 */
	TRGM	   *trigrams;
	/* 如果是正则表达式操作符，则提取的图 */
	TrgmPackedGraph *graph;

	/*
	 * "查询"和"三元组"与此缓存结构存储在同一个 palloc 块中，
	 * 以 MAXALIGN 对齐的偏移量存储。然而图形则不是。
	 */
} gtrgm_consistent_cache;

#define GETENTRY(vec,pos) ((TRGM *) DatumGetPointer((vec)->vector[(pos)].key))


PG_FUNCTION_INFO_V1(gtrgm_in);
PG_FUNCTION_INFO_V1(gtrgm_out);
PG_FUNCTION_INFO_V1(gtrgm_compress);
PG_FUNCTION_INFO_V1(gtrgm_decompress);
PG_FUNCTION_INFO_V1(gtrgm_consistent);
PG_FUNCTION_INFO_V1(gtrgm_distance);
PG_FUNCTION_INFO_V1(gtrgm_union);
PG_FUNCTION_INFO_V1(gtrgm_same);
PG_FUNCTION_INFO_V1(gtrgm_penalty);
PG_FUNCTION_INFO_V1(gtrgm_picksplit);
PG_FUNCTION_INFO_V1(gtrgm_options);


Datum gtrgm_in(PG_FUNCTION_ARGS)
{
	elog(ERROR, "not implemented");
	PG_RETURN_DATUM(0);
}

Datum gtrgm_out(PG_FUNCTION_ARGS)
{
	elog(ERROR, "not implemented");
	PG_RETURN_DATUM(0);
}

static TRGM * fc_gtrgm_alloc(bool fc_isalltrue, int fc_siglen, BITVECP fc_sign)
{
	int			fc_flag = SIGNKEY | (fc_isalltrue ? ALLISTRUE : 0);
	int			fc_size = CALCGTSIZE(fc_flag, fc_siglen);
	TRGM	   *fc_res = palloc(fc_size);

	SET_VARSIZE(fc_res, fc_size);
	fc_res->flag = fc_flag;

	if (!fc_isalltrue)
	{
		if (fc_sign)
			memcpy(GETSIGN(fc_res), fc_sign, fc_siglen);
		else
			memset(GETSIGN(fc_res), 0, fc_siglen);
	}

	return fc_res;
}

static void fc_makesign(BITVECP fc_sign, TRGM *fc_a, int fc_siglen)
{
	int32		fc_k,
				fc_len = ARRNELEM(fc_a);
	trgm	   *fc_ptr = GETARR(fc_a);
	int32		fc_tmp = 0;

	MemSet((void *) fc_sign, 0, fc_siglen);
	SETBIT(fc_sign, SIGLENBIT(fc_siglen));	/* 设置最后一个未使用位 */
	for (fc_k = 0; fc_k < fc_len; fc_k++)
	{
		CPTRGM(((char *) &fc_tmp), fc_ptr + fc_k);
		HASH(fc_sign, fc_tmp, fc_siglen);
	}
}

Datum gtrgm_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	int			fc_siglen = GET_SIGLEN();
	GISTENTRY  *fc_retval = fc_entry;

	if (fc_entry->leafkey)
	{							/* trgm */
		TRGM	   *fc_res;
		text	   *fc_val = DatumGetTextPP(fc_entry->key);

		fc_res = generate_trgm(VARDATA_ANY(fc_val), VARSIZE_ANY_EXHDR(fc_val));
		fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_res),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset, false);
	}
	else if (ISSIGNKEY(DatumGetPointer(fc_entry->key)) &&
			 !ISALLTRUE(DatumGetPointer(fc_entry->key)))
	{
		int32		i;
		TRGM	   *fc_res;
		BITVECP		fc_sign = GETSIGN(DatumGetPointer(fc_entry->key));

		LOOPBYTE(fc_siglen)
		{
			if ((fc_sign[i] & 0xff) != 0xff)
				PG_RETURN_POINTER(fc_retval);
		}

		fc_res = fc_gtrgm_alloc(true, fc_siglen, fc_sign);
		fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_res),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset, false);
	}
	PG_RETURN_POINTER(fc_retval);
}

Datum gtrgm_decompress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_retval;
	text	   *fc_key;

	fc_key = DatumGetTextPP(fc_entry->key);

	if (fc_key != (text *) DatumGetPointer(fc_entry->key))
	{
		/* 需要传回解压缩的项 */
		fc_retval = palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_key),
					  fc_entry->rel, fc_entry->page, fc_entry->offset, fc_entry->leafkey);
		PG_RETURN_POINTER(fc_retval);
	}
	else
	{
		/* 我们可以按原样返回条目 */
		PG_RETURN_POINTER(fc_entry);
	}
}

static int32 fc_cnt_sml_sign_common(TRGM *fc_qtrg, BITVECP fc_sign, int fc_siglen)
{
	int32		fc_count = 0;
	int32		fc_k,
				fc_len = ARRNELEM(fc_qtrg);
	trgm	   *fc_ptr = GETARR(fc_qtrg);
	int32		fc_tmp = 0;

	for (fc_k = 0; fc_k < fc_len; fc_k++)
	{
		CPTRGM(((char *) &fc_tmp), fc_ptr + fc_k);
		fc_count += GETBIT(fc_sign, HASHVAL(fc_tmp, fc_siglen));
	}

	return fc_count;
}

Datum gtrgm_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	text	   *fc_query = PG_GETARG_TEXT_P(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid		subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	int			fc_siglen = GET_SIGLEN();
	TRGM	   *fc_key = (TRGM *) DatumGetPointer(fc_entry->key);
	TRGM	   *fc_qtrg;
	bool		fc_res;
	Size		fc_querysize = VARSIZE(fc_query);
	gtrgm_consistent_cache *fc_cache;
	double		fc_nlimit;

	/*
	 * 我们将提取的三元组保存在缓存中，因为三元组提取
	 * 相对消耗 CPU。试图重用缓存值时，不仅要检查查询本身
	 * 的策略编号，因为三元组提取取决于策略。
	 *
	 * 缓存结构是一个包含 gtrgm_consistent_cache 头部的
	 * 单个 palloc 块，接着是输入查询（4 字节长度
	 * 单词，未压缩，从 MAXALIGN 边界开始），然后是 TRGM
	 * 值（同样从 MAXALIGN 边界开始）。然而我们不尝试
	 * 在该结构中包含正则表达式图（如果有的话）。（XXX 目前，这个
	 * 方法可能在索引重新扫描过程中泄漏正则表达式图。不清楚
	 * 是否值得修复。）
	 */
	fc_cache = (gtrgm_consistent_cache *) fcinfo->flinfo->fn_extra;
	if (fc_cache == NULL ||
		fc_cache->strategy != fc_strategy ||
		VARSIZE(fc_cache->query) != fc_querysize ||
		memcmp((char *) fc_cache->query, (char *) fc_query, fc_querysize) != 0)
	{
		gtrgm_consistent_cache *fc_newcache;
		TrgmPackedGraph *fc_graph = NULL;
		Size		fc_qtrgsize;

		switch (fc_strategy)
		{
			case SimilarityStrategyNumber:
			case WordSimilarityStrategyNumber:
			case StrictWordSimilarityStrategyNumber:
			case EqualStrategyNumber:
				fc_qtrg = generate_trgm(VARDATA(fc_query),
									 fc_querysize - VARHDRSZ);
				break;
			case ILikeStrategyNumber:
#ifndef IGNORECASE
				elog(ERROR, "cannot handle ~~* with case-sensitive trigrams");
#endif
				/* FALL THRU */
			case LikeStrategyNumber:
				fc_qtrg = generate_wildcard_trgm(VARDATA(fc_query),
											  fc_querysize - VARHDRSZ);
				break;
			case RegExpICaseStrategyNumber:
#ifndef IGNORECASE
				elog(ERROR, "cannot handle ~* with case-sensitive trigrams");
#endif
				/* FALL THRU */
			case RegExpStrategyNumber:
				fc_qtrg = createTrgmNFA(fc_query, PG_GET_COLLATION(),
									 &fc_graph, fcinfo->flinfo->fn_mcxt);
				/* 以防返回空数组 ... */
				if (fc_qtrg && ARRNELEM(fc_qtrg) <= 0)
				{
					pfree(fc_qtrg);
					fc_qtrg = NULL;
				}
				break;
			default:
				elog(ERROR, "unrecognized strategy number: %d", fc_strategy);
				fc_qtrg = NULL;	/* 保持编译器安静 */
				break;
		}

		fc_qtrgsize = fc_qtrg ? VARSIZE(fc_qtrg) : 0;

		fc_newcache = (gtrgm_consistent_cache *)
			MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
							   MAXALIGN(sizeof(gtrgm_consistent_cache)) +
							   MAXALIGN(fc_querysize) +
							   fc_qtrgsize);

		fc_newcache->strategy = fc_strategy;
		fc_newcache->query = (text *)
			((char *) fc_newcache + MAXALIGN(sizeof(gtrgm_consistent_cache)));
		memcpy((char *) fc_newcache->query, (char *) fc_query, fc_querysize);
		if (fc_qtrg)
		{
			fc_newcache->trigrams = (TRGM *)
				((char *) fc_newcache->query + MAXALIGN(fc_querysize));
			memcpy((char *) fc_newcache->trigrams, (char *) fc_qtrg, fc_qtrgsize);
			/* 如有必要，释放 qtrg，以防它是在 fn_mcxt 中创建的 */
			pfree(fc_qtrg);
		}
		else
			fc_newcache->trigrams = NULL;
		fc_newcache->graph = fc_graph;

		if (fc_cache)
			pfree(fc_cache);
		fcinfo->flinfo->fn_extra = (void *) fc_newcache;
		fc_cache = fc_newcache;
	}
#ifdef FDD //cppcheck
	if (NULL == fc_cache)
		PG_RETURN_BOOL(false);
#endif
	fc_qtrg = fc_cache->trigrams;

	switch (fc_strategy)
	{
		case SimilarityStrategyNumber:
		case WordSimilarityStrategyNumber:
		case StrictWordSimilarityStrategyNumber:

			/*
			 * 相似性搜索是精确的。（严格的）单词相似性搜索是
			 * 不精确的
			 */
			*fc_recheck = (fc_strategy != SimilarityStrategyNumber);

			fc_nlimit = index_strategy_get_limit(fc_strategy);

			if (GIST_LEAF(fc_entry))
			{					/* 所有叶子节点包含原始三元组 */
				double		fc_tmpsml = cnt_sml(fc_qtrg, fc_key, *fc_recheck);

				fc_res = (fc_tmpsml >= fc_nlimit);
			}
			else if (ISALLTRUE(fc_key))
			{					/* 非叶子节点包含签名 */
				fc_res = true;
			}
			else
			{					/* 非叶子节点包含签名 */
				int32		fc_count = fc_cnt_sml_sign_common(fc_qtrg, GETSIGN(fc_key), fc_siglen);
				int32		fc_len = ARRNELEM(fc_qtrg);

				if (fc_len == 0)
					fc_res = false;
				else
					fc_res = (((((float8) fc_count) / ((float8) fc_len))) >= fc_nlimit);
			}
			break;
		case ILikeStrategyNumber:
#ifndef IGNORECASE
			elog(ERROR, "cannot handle ~~* with case-sensitive trigrams");
#endif
			/* FALL THRU */
		case LikeStrategyNumber:
		case EqualStrategyNumber:
			/* 通配符和等于搜索是不精确的 */
			*fc_recheck = true;

			/*
			 * 检查所有提取的三元组是否可以出现在子节点中。
			 */
			if (GIST_LEAF(fc_entry))
			{					/* 所有叶子节点包含原始三元组 */
				fc_res = trgm_contained_by(fc_qtrg, fc_key);
			}
			else if (ISALLTRUE(fc_key))
			{					/* 非叶子节点包含签名 */
				fc_res = true;
			}
			else
			{					/* 非叶子节点包含签名 */
				int32		fc_k,
							fc_tmp = 0,
							fc_len = ARRNELEM(fc_qtrg);
				trgm	   *fc_ptr = GETARR(fc_qtrg);
				BITVECP		fc_sign = GETSIGN(fc_key);

				fc_res = true;
				for (fc_k = 0; fc_k < fc_len; fc_k++)
				{
					CPTRGM(((char *) &fc_tmp), fc_ptr + fc_k);
					if (!GETBIT(fc_sign, HASHVAL(fc_tmp, fc_siglen)))
					{
						fc_res = false;
						break;
					}
				}
			}
			break;
		case RegExpICaseStrategyNumber:
#ifndef IGNORECASE
			elog(ERROR, "cannot handle ~* with case-sensitive trigrams");
#endif
			/* FALL THRU */
		case RegExpStrategyNumber:
			/* 正则表达式搜索是不精确的 */
			*fc_recheck = true;

			/* 尽可能使用可用信息检查正则匹配 */
			if (fc_qtrg)
			{
				if (GIST_LEAF(fc_entry))
				{				/* 所有叶子节点包含原始三元组 */
					bool	   *fc_check;

					fc_check = trgm_presence_map(fc_qtrg, fc_key);
					fc_res = trigramsMatchGraph(fc_cache->graph, fc_check);
					pfree(fc_check);
				}
				else if (ISALLTRUE(fc_key))
				{				/* 非叶子节点包含签名 */
					fc_res = true;
				}
				else
				{				/* 非叶子节点包含签名 */
					int32		fc_k,
								fc_tmp = 0,
								fc_len = ARRNELEM(fc_qtrg);
					trgm	   *fc_ptr = GETARR(fc_qtrg);
					BITVECP		fc_sign = GETSIGN(fc_key);
					bool	   *fc_check;

					/*
					 * GETBIT() 测试可能会导致假阳性，因为
					 * 签名数组的大小有限。但由于 trigramsMatchGraph()
					 * 实现了单调布尔函数，检查数组中的假阳性
					 * 不会导致假阴性答案。因此，我们可以在不确定的情况下
					 * 应用 trigramsMatchGraph，这有助于提高搜索质量。
					 */
					fc_check = (bool *) palloc(fc_len * sizeof(bool));
					for (fc_k = 0; fc_k < fc_len; fc_k++)
					{
						CPTRGM(((char *) &fc_tmp), fc_ptr + fc_k);
						fc_check[fc_k] = GETBIT(fc_sign, HASHVAL(fc_tmp, fc_siglen));
					}
					fc_res = trigramsMatchGraph(fc_cache->graph, fc_check);
					pfree(fc_check);
				}
			}
			else
			{
				/* 不包含三元组的查询必须在各处重新检查 */
				fc_res = true;
			}
			break;
		default:
			elog(ERROR, "unrecognized strategy number: %d", fc_strategy);
			fc_res = false;		/* 保持编译器安静 */
			break;
	}

	PG_RETURN_BOOL(fc_res);
}

Datum gtrgm_distance(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	text	   *fc_query = PG_GETARG_TEXT_P(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid		subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	int			fc_siglen = GET_SIGLEN();
	TRGM	   *fc_key = (TRGM *) DatumGetPointer(fc_entry->key);
	TRGM	   *fc_qtrg;
	float8		fc_res;
	Size		fc_querysize = VARSIZE(fc_query);
	char	   *fc_cache = (char *) fcinfo->flinfo->fn_extra;

	/*
	 * 在多次调用相同查询时缓存生成的三元组。
	 */
	if (fc_cache == NULL ||
		VARSIZE(fc_cache) != fc_querysize ||
		memcmp(fc_cache, fc_query, fc_querysize) != 0)
	{
		char	   *fc_newcache;

		fc_qtrg = generate_trgm(VARDATA(fc_query), fc_querysize - VARHDRSZ);

		fc_newcache = MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
									  MAXALIGN(fc_querysize) +
									  VARSIZE(fc_qtrg));

		memcpy(fc_newcache, fc_query, fc_querysize);
		memcpy(fc_newcache + MAXALIGN(fc_querysize), fc_qtrg, VARSIZE(fc_qtrg));

		if (fc_cache)
			pfree(fc_cache);
		fcinfo->flinfo->fn_extra = fc_newcache;
		fc_cache = fc_newcache;
	}

	fc_qtrg = (TRGM *) (fc_cache + MAXALIGN(fc_querysize));

	switch (fc_strategy)
	{
		case DistanceStrategyNumber:
		case WordDistanceStrategyNumber:
		case StrictWordDistanceStrategyNumber:
			/* 只有纯三元组距离是精确的 */
			*fc_recheck = (fc_strategy != DistanceStrategyNumber);
			if (GIST_LEAF(fc_entry))
			{					/* 所有叶子节点包含原始三元组 */

				/*
				 * 防止gcc使用volatile关键字优化sml变量。
				 * 否则res可能与word_similarity_dist_op()函数不同。
				 */
				float4 volatile fc_sml = cnt_sml(fc_qtrg, fc_key, *fc_recheck);

				fc_res = 1.0 - fc_sml;
			}
			else if (ISALLTRUE(fc_key))
			{					/* 所有叶子节点包含原始三元组 */
				fc_res = 0.0;
			}
			else
			{					/* 非叶子节点包含签名 */
				int32		fc_count = fc_cnt_sml_sign_common(fc_qtrg, GETSIGN(fc_key), fc_siglen);
				int32		fc_len = ARRNELEM(fc_qtrg);

				fc_res = (fc_len == 0) ? -1.0 : 1.0 - ((float8) fc_count) / ((float8) fc_len);
			}
			break;
		default:
			elog(ERROR, "unrecognized strategy number: %d", fc_strategy);
			fc_res = 0;			/* 保持编译器安静 */
			break;
	}

	PG_RETURN_FLOAT8(fc_res);
}

static int32 fc_unionkey(BITVECP fc_sbase, TRGM *fc_add, int fc_siglen)
{
	int32		i;

	if (ISSIGNKEY(fc_add))
	{
		BITVECP		fc_sadd = GETSIGN(fc_add);

		if (ISALLTRUE(fc_add))
			return 1;

		LOOPBYTE(fc_siglen)
			fc_sbase[i] |= fc_sadd[i];
	}
	else
	{
		trgm	   *fc_ptr = GETARR(fc_add);
		int32		fc_tmp = 0;

		for (i = 0; i < ARRNELEM(fc_add); i++)
		{
			CPTRGM(((char *) &fc_tmp), fc_ptr + i);
			HASH(fc_sbase, fc_tmp, fc_siglen);
		}
	}
	return 0;
}


Datum gtrgm_union(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	int32		fc_len = fc_entryvec->n;
	int		   *fc_size = (int *) PG_GETARG_POINTER(1);
	int			fc_siglen = GET_SIGLEN();
	int32		fc_i;
	TRGM	   *fc_result = fc_gtrgm_alloc(false, fc_siglen, NULL);
	BITVECP		fc_base = GETSIGN(fc_result);

	for (fc_i = 0; fc_i < fc_len; fc_i++)
	{
		if (fc_unionkey(fc_base, GETENTRY(fc_entryvec, fc_i), fc_siglen))
		{
			fc_result->flag = ALLISTRUE;
			SET_VARSIZE(fc_result, CALCGTSIZE(ALLISTRUE, fc_siglen));
			break;
		}
	}

	*fc_size = VARSIZE(fc_result);

	PG_RETURN_POINTER(fc_result);
}

Datum gtrgm_same(PG_FUNCTION_ARGS)
{
	TRGM	   *fc_a = (TRGM *) PG_GETARG_POINTER(0);
	TRGM	   *fc_b = (TRGM *) PG_GETARG_POINTER(1);
	bool	   *fc_result = (bool *) PG_GETARG_POINTER(2);
	int			fc_siglen = GET_SIGLEN();

	if (ISSIGNKEY(fc_a))
	{							/* 那么b也也是ISSIGNKEY */
		if (ISALLTRUE(fc_a) && ISALLTRUE(fc_b))
			*fc_result = true;
		else if (ISALLTRUE(fc_a))
			*fc_result = false;
		else if (ISALLTRUE(fc_b))
			*fc_result = false;
		else
		{
			int32		i;
			BITVECP		fc_sa = GETSIGN(fc_a),
						fc_sb = GETSIGN(fc_b);

			*fc_result = true;
			LOOPBYTE(fc_siglen)
			{
				if (fc_sa[i] != fc_sb[i])
				{
					*fc_result = false;
					break;
				}
			}
		}
	}
	else
	{							/* a和b是ISARRKEY */
		int32		fc_lena = ARRNELEM(fc_a),
					fc_lenb = ARRNELEM(fc_b);

		if (fc_lena != fc_lenb)
			*fc_result = false;
		else
		{
			trgm	   *fc_ptra = GETARR(fc_a),
					   *fc_ptrb = GETARR(fc_b);
			int32		fc_i;

			*fc_result = true;
			for (fc_i = 0; fc_i < fc_lena; fc_i++)
				if (CMPTRGM(fc_ptra + fc_i, fc_ptrb + fc_i))
				{
					*fc_result = false;
					break;
				}
		}
	}

	PG_RETURN_POINTER(fc_result);
}

static int32 fc_sizebitvec(BITVECP fc_sign, int fc_siglen)
{
	return pg_popcount(fc_sign, fc_siglen);
}

static int fc_hemdistsign(BITVECP fc_a, BITVECP fc_b, int fc_siglen)
{
	int			i,
				fc_diff,
				fc_dist = 0;

	LOOPBYTE(fc_siglen)
	{
		fc_diff = (unsigned char) (fc_a[i] ^ fc_b[i]);
		/* 在这里使用 popcount 函数不太可能获胜 */
		fc_dist += pg_number_of_ones[fc_diff];
	}
	return fc_dist;
}

static int fc_hemdist(TRGM *fc_a, TRGM *fc_b, int fc_siglen)
{
	if (ISALLTRUE(fc_a))
	{
		if (ISALLTRUE(fc_b))
			return 0;
		else
			return SIGLENBIT(fc_siglen) - fc_sizebitvec(GETSIGN(fc_b), fc_siglen);
	}
	else if (ISALLTRUE(fc_b))
		return SIGLENBIT(fc_siglen) - fc_sizebitvec(GETSIGN(fc_a), fc_siglen);

	return fc_hemdistsign(GETSIGN(fc_a), GETSIGN(fc_b), fc_siglen);
}

Datum gtrgm_penalty(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* 始终 ISSIGNKEY */
	GISTENTRY  *fc_newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
	float	   *fc_penalty = (float *) PG_GETARG_POINTER(2);
	int			fc_siglen = GET_SIGLEN();
	TRGM	   *fc_origval = (TRGM *) DatumGetPointer(fc_origentry->key);
	TRGM	   *fc_newval = (TRGM *) DatumGetPointer(fc_newentry->key);
	BITVECP		fc_orig = GETSIGN(fc_origval);

	*fc_penalty = 0.0;

	if (ISARRKEY(fc_newval))
	{
		char	   *fc_cache = (char *) fcinfo->flinfo->fn_extra;
#ifdef FDD //CPPCHECK
		TRGM	   *fc_cachedVal = fc_cache != NULL ? (TRGM *) (fc_cache + MAXALIGN(fc_siglen)) : NULL;
#else
		TRGM	   *fc_cachedVal = (TRGM *) (fc_cache + MAXALIGN(fc_siglen));
#endif
		Size		fc_newvalsize = VARSIZE(fc_newval);
		BITVECP		fc_sign;

		/*
		 * 在多次调用相同newval时缓存签名数据。
		 */
		if (fc_cache == NULL ||
			VARSIZE(fc_cachedVal) != fc_newvalsize ||
			memcmp(fc_cachedVal, fc_newval, fc_newvalsize) != 0)
		{
			char	   *fc_newcache;

			fc_newcache = MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
										  MAXALIGN(fc_siglen) +
										  fc_newvalsize);

			fc_makesign((BITVECP) fc_newcache, fc_newval, fc_siglen);

			fc_cachedVal = (TRGM *) (fc_newcache + MAXALIGN(fc_siglen));
			memcpy(fc_cachedVal, fc_newval, fc_newvalsize);

			if (fc_cache)
				pfree(fc_cache);
			fcinfo->flinfo->fn_extra = fc_newcache;
			fc_cache = fc_newcache;
		}

		fc_sign = (BITVECP) fc_cache;

		if (ISALLTRUE(fc_origval))
			*fc_penalty = ((float) (SIGLENBIT(fc_siglen) - fc_sizebitvec(fc_sign, fc_siglen))) / (float) (SIGLENBIT(fc_siglen) + 1);
		else
			*fc_penalty = fc_hemdistsign(fc_sign, fc_orig, fc_siglen);
	}
	else
		*fc_penalty = fc_hemdist(fc_origval, fc_newval, fc_siglen);
	PG_RETURN_POINTER(fc_penalty);
}

typedef struct
{
	bool		allistrue;
	BITVECP		sign;
} CACHESIGN;

static void fc_fillcache(CACHESIGN *fc_item, TRGM *fc_key, BITVECP fc_sign, int fc_siglen)
{
	fc_item->allistrue = false;
	fc_item->sign = fc_sign;
	if (ISARRKEY(fc_key))
		fc_makesign(fc_item->sign, fc_key, fc_siglen);
	else if (ISALLTRUE(fc_key))
		fc_item->allistrue = true;
	else
		memcpy((void *) fc_item->sign, (void *) GETSIGN(fc_key), fc_siglen);
}

#define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
typedef struct
{
	OffsetNumber pos;
	int32		cost;
} SPLITCOST;

static int fc_comparecost(const void *fc_a, const void *fc_b)
{
	if (((const SPLITCOST *) fc_a)->cost == ((const SPLITCOST *) fc_b)->cost)
		return 0;
	else
		return (((const SPLITCOST *) fc_a)->cost > ((const SPLITCOST *) fc_b)->cost) ? 1 : -1;
}


static int fc_hemdistcache(CACHESIGN *fc_a, CACHESIGN *fc_b, int fc_siglen)
{
	if (fc_a->allistrue)
	{
		if (fc_b->allistrue)
			return 0;
		else
			return SIGLENBIT(fc_siglen) - fc_sizebitvec(fc_b->sign, fc_siglen);
	}
	else if (fc_b->allistrue)
		return SIGLENBIT(fc_siglen) - fc_sizebitvec(fc_a->sign, fc_siglen);

	return fc_hemdistsign(fc_a->sign, fc_b->sign, fc_siglen);
}

Datum gtrgm_picksplit(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	OffsetNumber fc_maxoff = fc_entryvec->n - 1;
	GIST_SPLITVEC *fc_v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	int			fc_siglen = GET_SIGLEN();
	OffsetNumber fc_k,
				j;
	TRGM	   *fc_datum_l,
			   *fc_datum_r;
	BITVECP		fc_union_l,
				fc_union_r;
	int32		fc_size_alpha,
				fc_size_beta;
	int32		fc_size_waste,
				fc_waste = -1;
	int32		fc_nbytes;
	OffsetNumber fc_seed_1 = 0,
				fc_seed_2 = 0;
	OffsetNumber *fc_left,
			   *fc_right;
	BITVECP		fc_ptr;
	int			i;
	CACHESIGN  *fc_cache;
	char	   *fc_cache_sign;
	SPLITCOST  *fc_costvector;

	/* 为每个现有项缓存签名数据 */
	fc_cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (fc_maxoff + 1));
	fc_cache_sign = palloc(fc_siglen * (fc_maxoff + 1));

	for (fc_k = FirstOffsetNumber; fc_k <= fc_maxoff; fc_k = OffsetNumberNext(fc_k))
		fc_fillcache(&fc_cache[fc_k], GETENTRY(fc_entryvec, fc_k), &fc_cache_sign[fc_siglen * fc_k],
				  fc_siglen);

	/* 现在找到两个相隔最远的项 */
	for (fc_k = FirstOffsetNumber; fc_k < fc_maxoff; fc_k = OffsetNumberNext(fc_k))
	{
		for (j = OffsetNumberNext(fc_k); j <= fc_maxoff; j = OffsetNumberNext(j))
		{
			fc_size_waste = fc_hemdistcache(&(fc_cache[j]), &(fc_cache[fc_k]), fc_siglen);
			if (fc_size_waste > fc_waste)
			{
				fc_waste = fc_size_waste;
				fc_seed_1 = fc_k;
				fc_seed_2 = j;
			}
		}
	}

	/* 以防我们没有进行选择…… */
	if (fc_seed_1 == 0 || fc_seed_2 == 0)
	{
		fc_seed_1 = 1;
		fc_seed_2 = 2;
	}

	/* 初始化结果向量 */
	fc_nbytes = fc_maxoff * sizeof(OffsetNumber);
	fc_v->spl_left = fc_left = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_right = fc_right = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_nleft = 0;
	fc_v->spl_nright = 0;

	/* 形成初始 .. */
	fc_datum_l = fc_gtrgm_alloc(fc_cache[fc_seed_1].allistrue, fc_siglen, fc_cache[fc_seed_1].sign);
	fc_datum_r = fc_gtrgm_alloc(fc_cache[fc_seed_2].allistrue, fc_siglen, fc_cache[fc_seed_2].sign);

	fc_union_l = GETSIGN(fc_datum_l);
	fc_union_r = GETSIGN(fc_datum_r);

	/* 在 ... 之前排序 */
	fc_costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * fc_maxoff);
	for (j = FirstOffsetNumber; j <= fc_maxoff; j = OffsetNumberNext(j))
	{
		fc_costvector[j - 1].pos = j;
		fc_size_alpha = fc_hemdistcache(&(fc_cache[fc_seed_1]), &(fc_cache[j]), fc_siglen);
		fc_size_beta = fc_hemdistcache(&(fc_cache[fc_seed_2]), &(fc_cache[j]), fc_siglen);
		fc_costvector[j - 1].cost = abs(fc_size_alpha - fc_size_beta);
	}
	qsort((void *) fc_costvector, fc_maxoff, sizeof(SPLITCOST), fc_comparecost);

	for (fc_k = 0; fc_k < fc_maxoff; fc_k++)
	{
		j = fc_costvector[fc_k].pos;
		if (j == fc_seed_1)
		{
			*fc_left++ = j;
			fc_v->spl_nleft++;
			continue;
		}
		else if (j == fc_seed_2)
		{
			*fc_right++ = j;
			fc_v->spl_nright++;
			continue;
		}

		if (ISALLTRUE(fc_datum_l) || fc_cache[j].allistrue)
		{
			if (ISALLTRUE(fc_datum_l) && fc_cache[j].allistrue)
				fc_size_alpha = 0;
			else
				fc_size_alpha = SIGLENBIT(fc_siglen) -
					fc_sizebitvec((fc_cache[j].allistrue) ? GETSIGN(fc_datum_l) :
							   GETSIGN(fc_cache[j].sign),
							   fc_siglen);
		}
		else
			fc_size_alpha = fc_hemdistsign(fc_cache[j].sign, GETSIGN(fc_datum_l), fc_siglen);

		if (ISALLTRUE(fc_datum_r) || fc_cache[j].allistrue)
		{
			if (ISALLTRUE(fc_datum_r) && fc_cache[j].allistrue)
				fc_size_beta = 0;
			else
				fc_size_beta = SIGLENBIT(fc_siglen) -
					fc_sizebitvec((fc_cache[j].allistrue) ? GETSIGN(fc_datum_r) :
							   GETSIGN(fc_cache[j].sign),
							   fc_siglen);
		}
		else
			fc_size_beta = fc_hemdistsign(fc_cache[j].sign, GETSIGN(fc_datum_r), fc_siglen);

		if (fc_size_alpha < fc_size_beta + WISH_F(fc_v->spl_nleft, fc_v->spl_nright, 0.1))
		{
			if (ISALLTRUE(fc_datum_l) || fc_cache[j].allistrue)
			{
				if (!ISALLTRUE(fc_datum_l))
					MemSet((void *) GETSIGN(fc_datum_l), 0xff, fc_siglen);
			}
			else
			{
				fc_ptr = fc_cache[j].sign;
				LOOPBYTE(fc_siglen)
					fc_union_l[i] |= fc_ptr[i];
			}
			*fc_left++ = j;
			fc_v->spl_nleft++;
		}
		else
		{
			if (ISALLTRUE(fc_datum_r) || fc_cache[j].allistrue)
			{
				if (!ISALLTRUE(fc_datum_r))
					MemSet((void *) GETSIGN(fc_datum_r), 0xff, fc_siglen);
			}
			else
			{
				fc_ptr = fc_cache[j].sign;
				LOOPBYTE(fc_siglen)
					fc_union_r[i] |= fc_ptr[i];
			}
			*fc_right++ = j;
			fc_v->spl_nright++;
		}
	}

	fc_v->spl_ldatum = PointerGetDatum(fc_datum_l);
	fc_v->spl_rdatum = PointerGetDatum(fc_datum_r);

	PG_RETURN_POINTER(fc_v);
}

Datum gtrgm_options(PG_FUNCTION_ARGS)
{
	local_relopts *fc_relopts = (local_relopts *) PG_GETARG_POINTER(0);

	init_local_reloptions(fc_relopts, sizeof(TrgmGistOptions));
	add_local_int_reloption(fc_relopts, "siglen",
							"signature length in bytes",
							SIGLEN_DEFAULT, 1, SIGLEN_MAX,
							offsetof(TrgmGistOptions, siglen));

	PG_RETURN_VOID();
}
